<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<HTML>
<HEAD>
 <META NAME="GENERATOR" CONTENT="SGML-Tools 1.0.9">
 <TITLE>The VFLib Graph Matching Library, version 2.0: Introduction </TITLE>
 <LINK HREF="vflib-2.html" REL=next>

 <LINK HREF="vflib.html#toc1" REL=contents>
</HEAD>
<BODY>
<A HREF="vflib-2.html">Next</A>
Previous
<A HREF="vflib.html#toc1">Contents</A>
<HR>
<H2><A NAME="Introduction"></A> <A NAME="s1">1. Introduction </A></H2>

<P> This document describes the <B>VFLib</B> graph matching library,
developed at the <EM>Intelligent Systems and Artificial Vision Lab.</EM>
(<EM>SIVALab</EM>) of the University of Naples ``Federico II''.
<P>The library has been developed mainly to test a new graph matching 
algorithm, named <B>VF</B>, and to compare it with other known algorithms,
like Ullmann's algorithm and the algorithm by Schmidt and Druffel
(see section 
<A HREF="vflib-30.html#References">References</A>).
<P>By no means VFLib attempts at providing a general graph library; it 
addresses only the problems of exact graph isomorphism and graph-subgraph
isomorphism. If you need to solve other graph problems, you should look for
a different tool, such as the 
<A HREF="http://www.algorithmic-solutions.com">LEDA Library</A>.
<P>The root of VFLib is a graph matching program, named <CODE>grapp</CODE>, which was
built in 1997 to compare the VF graph matching algorithm with Ullmann's.
The <CODE>grapp</CODE> program sources (written in C++)  have been made available 
on the World Wide Web since June 1997, and several researchers in different 
fields have downloaded it for their research activity.
<P>The <CODE>grapp</CODE> program was limited to only graph isomorphism, though the
paper describing the VF algorithm also presented its application to
graph-subgraph isomorphism; another limitation was that 
the program did not make provisions for associating
semantic attributes to the nodes and the edges of the graphs.
<P>Successively, the code was re-organized as a separate library (for which
the VFLib name was coined) to be linked with a main program, in order to
make easy the reuse the matching code in different applications.
At the same time, graph-subgraph isomorphism was added  
(both by means of  VF and of Ullmann's algorithm) and
a limited support for graph monomorphism was also introduced. 
Moreover, the data representation
was modified to deal with node and edge attributes, and accordingly
the algorithm implementations were changed to take advantage of
this semantic information when available.
<P>This version of VFLib (called 1.0) was never released to the public
(mostly because it was completely undocumented), 
but it has been used extensively for other projects in our Lab,
including the development of a Machine Learning system named
<B>Gengis</B> (see section 
<A HREF="vflib-30.html#References">References</A>).
<P>In 2000, in order to make the library work more efficiently on large
graphs, the data structures used for representing the graphs have been 
changed. We have also modified for this purpose the VF algorithm, 
defining an improved version named VF2, which lowers the memory
requirements from O(n^2) to O(n) with respect to the number of nodes
in the graphs. 
Also, after the suggestion of a reviewer of a paper of ours describing
VF, we have added support for the algorithm by Schmidt and Druffel.
<P>These changes led to version 2.0 of VFLib, which we have made now
available on the Internet. The documentation you are reading refers to
VFLib 2.0; you may check the 
<A HREF="http://amalfi.dis.unina.it/graph">SIVALab graph matching page</A> for further updates of this library.
On that page you will also find the <EM>Graph Database</EM>, a huge collection
of graphs aimed at becoming a common data set for benchmarking
graph matching algorithms.
<P>
<P>
<P>
<P>
<HR>
<A HREF="vflib-2.html">Next</A>
Previous
<A HREF="vflib.html#toc1">Contents</A>
</BODY>
</HTML>
